package 排序算法.归并排序;

public class Merge_sort {

    public static void main(String[] args) {
        int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
        System.out.println("排序之前：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
        //归并排序
        mergeSort(a,0,a.length-1);
        System.out.println();
        System.out.println("排序之后：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }

    private static void mergeSort(int[] a, int left, int right) {
        if (left<right){
            int middle= (left+right)/2;
            mergeSort(a,left,middle);
            mergeSort(a,middle+1 ,right);
            //合并
            merge(a,left,middle,right);
        }
    }

    private static void merge(int[] a, int left, int middle, int right) {
        //将两个有序数组合并 left——middle   middle+1——right
        int[] tmpArr = new int[a.length];
        int rightBegin=middle+1;
        int tempLeft=left;
        int tempIndex=left;
        while (left<=middle && rightBegin<=right){
            if (a[left]<=a[rightBegin]){
                tmpArr[tempIndex++]=a[left++];
            }else {
                tmpArr[tempIndex++]=a[rightBegin++];
            }
        }
        while (left<=middle){
            tmpArr[tempIndex++]=a[left++];
        }
        while (rightBegin<=right){
            tmpArr[tempIndex++]=a[rightBegin++];
        }
        while (tempLeft<=right){
            a[tempLeft]=tmpArr[tempLeft++];
        }
    }
}
